package tulingxueyuan117;

import java.util.Arrays;

/**
 * Author: Zhang Dongwei
 * Date: 2022/11/6 14:52
 * 插入升序排序
 */
public class p34_插入排序_912 {
    public static void main(String[] args) {
        int[] arr = {86,39,77,23,32,45,58,63,93,4,37,22};
        System.out.println(Arrays.toString(arr));
        System.out.println("=========================");
        int[] res = insertSort(arr);
        System.out.println("=========================");
        System.out.println(Arrays.toString(res));
    }

//    每轮选择最小的放在最前面， 超时
    public static int[] insertSort(int[] arr) {
        if(arr.length==0) return arr;
        int currentValue;  // 当前待排序的数据，该元素之前的元素是已经排好序的
        for (int i = 0; i<arr.length-1; i++){
            int preIndex = i;  // 用于标志已经排序的索引
            currentValue = arr[preIndex+1];
            while (preIndex>=0&&currentValue<arr[preIndex]){
                arr[preIndex+1] = arr[preIndex];  // 元素后移一位
                preIndex--;
            }
            arr[preIndex+1] = currentValue;
            System.out.println(Arrays.toString(arr));
        }
        return arr;
    }

    public static int[] insertSort1(int[] arr) {
        if(arr.length==0) return arr;
        int currentValue;
        for(int i=0; i<arr.length-1; i++){
            int preIndex = i;
            currentValue = arr[preIndex+1];
            while (preIndex>=0&&currentValue<arr[preIndex]){
                arr[preIndex+1] = arr[preIndex];
                preIndex--;
            }
            arr[preIndex+1] = currentValue;
            System.out.println(Arrays.toString(arr));
        }
        return arr;
    }
}
